// 113. [dfs递归二叉树前序遍历] 路径总和 II
// https://leetcode.cn/problems/path-sum-ii/
//给你二叉树的根节点 root 和一个整数目标和 targetSum ，
//找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//叶子节点 是指没有子节点的节点。
//示例 1：
//输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//输出：[[5,4,11,2],[5,8,4,5]]

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode* left, TreeNode* right)
      : val(x), left(left), right(right) {}
};
class Solution {
  void dfsTree(TreeNode* root, int targetSum, int cur, vector<int>& path,
               vector<vector<int>>& ans) {
    if (!root) {
      return;
    }
    cur += root->val;
    path.push_back(root->val);
    if (!root->left && !root->right) {
      if (targetSum == cur) {
        ans.push_back(path);
      }
    }
    dfsTree(root->left, targetSum, cur, path, ans);
    dfsTree(root->right, targetSum, cur, path, ans);
    path.pop_back();
  }

 public:
  vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<int> path;
    vector<vector<int>> ans;
    dfsTree(root, targetSum, 0, path, ans);
    return ans;
  }
};
